#include <iostream>
#include <assert.h>
using namespace std;

namespace my_list
{
	template <class T>
	struct ListNode
	{
		T _val;
		ListNode* _next;
		ListNode* _prev;
		ListNode(T val) :_val(val), _next(nullptr), _prev(nullptr)
		{
			;
		}
	};

	template <class T>
	class List
	{
		typedef ListNode<T> iterator;
		typedef const ListNode<T> const_iterator;

		List() :head(nullptr), _size = 0
		{
			head = new ListNode;
		}

		List(const& T val)
		{
			head = new ListNode;
			head->_next = head->_prev = new ListNode(val);
			_size = 1;
		}

		List(const ListNode<T>* list)
		{
			assert(list);
			ListNode<T>* newhead = new ListNode(list->_val);
			newhead->_val = list->_val;
			head = newhead;
			ListNode<T> * cur = list->_next;
			_size = 0;
			while (cur != list && cur->_next != list)
			{
				newhead->_next = new ListNode(cur->_next->_val);
				_size++;
			}
		}

		~List()
		{
			ListNode<T>* cur = head->_next;
			while (cur)
			{
				ListNode* next = cur->_next;
				delete cur;
				cur = next;
			}
			delete head;
			head = nullptr;
			_size = 0;
		}

		void push_back(const T& val)
		{
			ListNode<T>* cur = new ListNode(val);
			head->_prev->_next = cur;
			cur->_next = head;
			head->_prev = cur;
			_size++;
		}

		void push_front(const T& val)
		{
			ListNode<T>* cur = new ListNode(val);
			head->_next->_prev = cur;
			cur->_prev = head;
			head->_next = cur;
			_size++;
		}

		void pop_back()
		{
			assert(head->_next != head);
			ListNode<T>* cur = head->_prev;
			head->_prev = cur->_prev;
			head->_prev->_next = head;
			delete cur;
			_size--;
		}

		void pop_front()
		{
			assert(head->_next != head);
			ListNode<T>* cur = head->_next;
			head->_next = cur->_next;
			head->_next->_prev = head;
			delete cur;
			_size--;
		}

		void clear()
		{
			ListNode<T>* cur = head->_next;
			while (cur != head)
			{
				ListNode<T>* next = cur->_next;
				delete cur;
				cur = cur->_next;
			}
			head->_next = head->_prev = nullptr;
		}

		iterator begin()
		{
			return head->_next;
		}

		iterator end()
		{
			return head->_prev;
		}

		iterator operator++(iterator cur)
		{
			return cur->_next;
		}

		iterator operator--(iterator cur)
		{
			return cur->_prev;
		}

		const_iterator cend()const
		{
			return head->_prev;
		}

		const_iterator cend()const
		{
			return head->_prev;
		}

		size_t size()
		{
			return _size;
		}

		ListNode<T>* head;
		size_t _size;
	};
}
